home *** CD-ROM | disk | FTP | other *** search
/ QRZ! Ham Radio 6 / QRZ Ham Radio Callsign Database - Volume 6.iso / mac / files / amiga / rhinosrc.lha / alloc.c next >
C/C++ Source or Header  |  1993-07-04  |  15KB  |  654 lines
  1. /* memory allocation routines
  2.  * Copyright 1991 Phil Karn, KA9Q
  3.  *
  4.  * Adapted from alloc routine in K&R; memory statistics and interrupt
  5.  * protection added for use with net package. Must be used in place of
  6.  * standard Turbo-C library routines because the latter check for stack/heap
  7.  * collisions. This causes erroneous failures because process stacks are
  8.  * allocated off the heap.
  9.  */
  10.  
  11. #include <stdio.h>
  12. #ifdef MSDOS
  13. #include <dos.h>
  14. #include <alloc.h>
  15. #endif
  16. #include "global.h"
  17. #include "mbuf.h"
  18. #include "proc.h"
  19. #include "cmdparse.h"
  20.  
  21. #ifdef AMIGA
  22. #define LIBRARIES_MATHFFP_H    /* Don't include this one! */
  23. #include <exec/lists.h>
  24. #include <exec/memory.h>
  25. #include <clib/exec_protos.h>
  26. #include <clib/alib_protos.h>
  27. #ifdef __SASC
  28. #include <pragmas/exec_sysbase_pragmas.h>
  29. #endif
  30. extern struct ExecBase *SysBase;
  31. #endif
  32.  
  33. static unsigned long Memfail;    /* Count of allocation failures */
  34. static unsigned long Allocs;    /* Total allocations */
  35. static unsigned long Frees;    /* Total frees */
  36. static unsigned long Invalid;    /* Total calls to free with garbage arg */
  37. static unsigned long Intalloc;    /* Calls to malloc with ints disabled */
  38. static unsigned long Intfree;    /* Calls to free with ints disabled */
  39. static int Memwait;        /* Number of tasks waiting for memory */
  40. static unsigned long Yellows;    /* Yellow alert garbage collections */
  41. static unsigned long Reds;    /* Red alert garbage collections */
  42. unsigned long Availmem;     /* Heap memory, ABLKSIZE units */
  43. static unsigned long Morecores;
  44.  
  45. static unsigned long Sizes[16];
  46.  
  47. static int dostat __ARGS((int argc,char *argv[],void *p));
  48. static int dofreelist __ARGS((int argc,char *argv[],void *p));
  49. static int doibufsize __ARGS((int argc,char *argv[],void *p));
  50. static int donibufs __ARGS((int argc,char *argv[],void *p));
  51. static int dothresh __ARGS((int argc,char *argv[],void *p));
  52. static int dosizes __ARGS((int argc,char *argv[],void *p));
  53. int domem(int argc, char *argv[], void *p);
  54. void gcollect(int i, void *v1, void *v2);
  55.  
  56. struct cmds Memcmds[] = {
  57.     "freelist",     dofreelist,     0, 0, NULLCHAR,
  58.     "ibufsize",     doibufsize,     0, 0, NULLCHAR,
  59.     "nibufs",       donibufs,       0, 0, NULLCHAR,
  60.     "sizes",        dosizes,        0, 0, NULLCHAR,
  61.     "status",       dostat,         0, 0, NULLCHAR,
  62.     "thresh",       dothresh,       0, 0, NULLCHAR,
  63.     NULLCHAR,
  64. };
  65.  
  66. #if defined(MSDOS) && defined(LARGEDATA)
  67. #define HUGE    huge
  68. #else
  69. #define HUGE
  70. #endif
  71.  
  72. union header {
  73.     struct {
  74.         union header HUGE *ptr;
  75.         unsigned long size;
  76.     } s;
  77.     long l[2];
  78. };
  79.  
  80. typedef union header HEADER;
  81. #define NULLHDR (HEADER HUGE *)NULL
  82.  
  83. #define ABLKSIZE    (sizeof (HEADER))
  84.  
  85. static HEADER HUGE *morecore __ARGS((unsigned nu));
  86.  
  87. static HEADER Base;
  88. static HEADER HUGE *Allocp = NULLHDR;
  89. static unsigned long Heapsize;
  90.  
  91. #ifdef MSDOS
  92. /* Memory blocks obtained from MS-DOS by allocmem() call */
  93. struct sysblock {
  94.     unsigned seg;
  95.     unsigned npar;
  96. };
  97. #define NSYSBLOCK    5
  98. struct sysblock Sysblock[NSYSBLOCK];
  99. #endif
  100. #ifdef AMIGA
  101. struct MemBlock {
  102.     struct MinNode    Node;
  103.     long        Size;
  104.     long        pad;    /* size multiple of 8==ABLKSIZE */
  105. };
  106. struct MinList SysBlocks;
  107. static void freeblocks(void);
  108. static int Delayfree;        /* freeblocks() is slow - don't do it too often */
  109. #define ALLOCMEMSIZE    8192
  110.  
  111. void *
  112. NextNode(void *n)
  113. {
  114.     struct Node *nn;
  115.  
  116.     nn = ((struct Node *)n)->ln_Succ;
  117.     if (nn->ln_Pred != n)
  118.         log(-1, "List inconsistent: pred(%x) == %x != %x\n", nn, 
  119.             nn->ln_Pred, n);
  120.     if (nn->ln_Succ)
  121.         return nn;
  122.     return NULL;
  123. }
  124. #endif
  125.  
  126. /* Allocate block of 'nb' bytes */
  127. void *
  128. malloc(nb)
  129. unsigned nb;
  130. {
  131.     register HEADER HUGE *p, HUGE *q;
  132.     register unsigned nu;
  133.     int i;
  134.  
  135.     if(!istate())
  136.         Intalloc++;
  137.     if(nb == 0)
  138.         return NULL;
  139.  
  140.     /* Record the size of this request */
  141.     if((i = log2(nb)) >= 0)
  142.         Sizes[i]++;
  143.  
  144.     /* Round up to full block, then add one for header */
  145.     nu = ((nb + ABLKSIZE - 1) / ABLKSIZE) + 1;
  146.     if((q = Allocp) == NULLHDR){
  147.         Base.s.ptr = Allocp = q = &Base;
  148.         Base.s.size = 1;
  149. #ifdef AMIGA
  150.         NewList((struct List *)&SysBlocks);
  151. #endif
  152.     }
  153.     for(p = q->s.ptr; ; q = p, p = p->s.ptr){
  154.         if(p->s.size >= nu){
  155.             /* This chunk is at least as large as we need */
  156.             if(p->s.size <= nu + 1){
  157.                 /* This is either a perfect fit (size == nu)
  158.                  * or the free chunk is just one unit larger.
  159.                  * In either case, alloc the whole thing,
  160.                  * because there's no point in keeping a free
  161.                  * block only large enough to hold the header.
  162.                  */
  163.                 q->s.ptr = p->s.ptr;
  164.             } else {
  165.                 /* Carve out piece from end of entry */
  166.                 p->s.size -= nu;
  167.                 p += p->s.size;
  168.                 p->s.size = nu;
  169.             }
  170. #ifdef    circular
  171.             Allocp = q;
  172. #endif
  173.             p->s.ptr = p;    /* for auditing */
  174.             Allocs++;
  175.             Availmem -= p->s.size;
  176.             p++;
  177.             break;
  178.         }
  179.         if(p == Allocp && ((p = morecore(nu)) == NULLHDR)){
  180.             Memfail++;
  181.             break;
  182.         }
  183.     }
  184. #if defined(LARGEDATA) && defined(MSDOS)
  185.     /* On the brain-damaged Intel CPUs in "large data" model,
  186.      * make sure the pointer's offset field isn't null
  187.      * (unless the entire pointer is null).
  188.      * The Turbo C compiler and certain
  189.      * library functions like strrchr() assume this.
  190.      */
  191.     if(FP_OFF(p) == 0 && FP_SEG(p) != 0){
  192.         /* Return denormalized but equivalent pointer */
  193.         return (void *)MK_FP(FP_SEG(p)-1,16);
  194.     }
  195. #endif
  196.     return (void *)p;
  197. }
  198. /* Get more memory from the system and put it on the heap */
  199. static HEADER HUGE *
  200. morecore(nu)
  201. unsigned nu;
  202. {
  203. #ifdef MSDOS
  204.     char HUGE *cp;
  205.     HEADER HUGE *up;
  206.     unsigned size;
  207.     unsigned segp;
  208.     unsigned npar;
  209.     struct sysblock *sp;
  210.     int i;
  211.  
  212.     Morecores++;
  213.     size = nu * ABLKSIZE;
  214.     /* First try to expand our main memory block */
  215.     if ((int)(cp = (char HUGE *)sbrk(size)) != -1){
  216.         up = (HEADER *)cp;
  217.         up->s.size = nu;
  218.         up->s.ptr = up; /* satisfy audit */
  219.         free((void *)(up + 1));
  220.         Heapsize += size;
  221.         Frees--;    /* Nullify increment inside free() */
  222.         return Allocp;
  223.     }
  224.     /* That failed; the main memory block must have grown into another
  225.      * allocated block, or something else (e.g., the increase handles
  226.      * call in ioinit()) must have allocated memory just beyond it.
  227.      * Allocate or extend an additional memory block.
  228.      */
  229.     npar = (size+16)/16;    /* Convert size from bytes to paragraphs */
  230.     cp = NULL;
  231.     for(sp=Sysblock,i=0;i < NSYSBLOCK;i++,sp++){
  232.         if(sp->npar != 0){
  233.             /* Try to expand this block */
  234.             if(setblock(sp->seg,sp->npar + npar) != -1){
  235.                 /* Failed (-1 == SUCCESS; strange!) */
  236.                 continue;
  237.             }
  238.             /* Block expansion succeeded */
  239.             cp = MK_FP(sp->seg + sp->npar,0);
  240.             sp->npar += npar;
  241.         } else {
  242.             /* Allocate new block */
  243.             if(allocmem(npar,&segp) != -1){
  244.                 return NULL;    /* Complete failure */
  245.             }
  246.             /* -1 indicates SUCCESS (strange) */
  247.             sp->seg = segp;
  248.             sp->npar = npar;
  249.             cp = MK_FP(segp,0);
  250.         }
  251.         break;
  252.     }
  253. #endif
  254. #ifdef AMIGA
  255.     char *cp;
  256.     HEADER *up;
  257.     unsigned long size;
  258.     unsigned npar;
  259.  
  260.     Morecores++;
  261.     size = nu * ABLKSIZE;
  262.     /* add MemBlock and make a full nr of intel paragraphs */
  263.     size = (size + sizeof(struct MemBlock) + 15) & ~15;
  264.     size = max(size, ALLOCMEMSIZE); /* blocks of 8K or more */
  265.     cp = AllocMem(size, MEMF_PUBLIC);
  266.     if (cp) {
  267.         ((struct MemBlock *)cp)->Size = size;
  268.         AddTail((struct List *)&SysBlocks, (struct Node *)cp);
  269.         cp += sizeof(struct MemBlock);
  270.         npar = (size-sizeof(struct MemBlock))/16;    /* Convert size from bytes to paragraphs */
  271.         Delayfree++;
  272.     }
  273. #endif
  274.     if(cp != (char HUGE *)NULL){
  275.         /* Expand or create succeeded, add to heap */
  276.         up = (HEADER *)cp;
  277.         up->s.size = (npar*16)/ABLKSIZE;
  278.         up->s.ptr = up; /* satisfy audit */
  279.         free((void *)(up + 1));
  280.         Heapsize += npar*16;
  281.         Frees--;    /* Nullify increment inside free() */
  282.         return Allocp;
  283.     }
  284.     return NULL;
  285. }
  286.  
  287. /* Put memory block back on heap */
  288. void
  289. free(blk)
  290. void *blk;
  291. {
  292.     register HEADER HUGE *p, HUGE *q;
  293.     unsigned short HUGE *ptr;
  294.  
  295.     if(!istate())
  296.         Intfree++;
  297.     if(blk == NULL)
  298.         return;     /* Required by ANSI */
  299.     p = (HEADER HUGE *)blk - 1;
  300.     /* Audit check */
  301.     if(p->s.ptr != p){
  302.         printf("free: WARNING! invalid pointer (0x%lx) proc %s\n",
  303.          ptol(blk),Curproc->name);
  304.         stktrace();
  305.         Invalid++;
  306. #ifdef MSDOS
  307.         ptr = (unsigned short *)&blk;
  308.         log(-1,"free: WARNING! invalid pointer (0x%lx) pc = 0x%x %x proc %s\n",
  309.          ptol(blk),ptr[-1],ptr[-2],Curproc->name);
  310. #endif
  311. #ifdef AMIGA
  312.         /* Sorry, this is probably very SAS/C 6.x specific...
  313.          * Stack layout:
  314.          * <return addr>
  315.          * <auto variable(s): ptr>
  316.          * <saved registers>
  317.          * Note there is no frame pointer, and no pushed args.
  318.          */
  319.         ptr = (unsigned short *)&ptr;
  320.         log(-1,"free: WARNING! invalid pointer (0x%lx) pc = 0x%06x proc %s\n",
  321.          blk,((unsigned long *)ptr)[1],Curproc->name);
  322. #endif
  323.         return;
  324.     }
  325.     Availmem += p->s.size;
  326.     /* Search the free list looking for the right place to insert */
  327.     for(q = Allocp; !(p > q && p < q->s.ptr); q = q->s.ptr){
  328.         /* Highest address on circular list? */
  329.         if(q >= q->s.ptr && (p > q || p < q->s.ptr))
  330.             break;
  331.     }
  332.     if(p + p->s.size == q->s.ptr){
  333.         /* Combine with front of this entry */
  334.         p->s.size += q->s.ptr->s.size;
  335.         p->s.ptr = q->s.ptr->s.ptr;
  336.     } else {
  337.         /* Link to front of this entry */
  338.         p->s.ptr = q->s.ptr;
  339.     }
  340.     if(q + q->s.size == p){
  341.         /* Combine with end of this entry */
  342.         q->s.size += p->s.size;
  343.         q->s.ptr = p->s.ptr;
  344.     } else {
  345.         /* Link to end of this entry */
  346.         q->s.ptr = p;
  347.     }
  348. #ifdef    circular
  349.     Allocp = q;
  350. #endif
  351.     Frees++;
  352.     if(Memwait != 0)
  353.         psignal(&Memwait,0);
  354. #ifdef AMIGA
  355.     else if ((Availmem * (ABLKSIZE / 2)) > Memthresh)
  356.         freeblocks();
  357. #endif
  358. }
  359.  
  360. #ifdef AMIGA
  361. void
  362. freeall(void)
  363. {
  364.     struct MemBlock *p;
  365.  
  366.     while (p = (struct MemBlock *)RemHead((struct List *)&SysBlocks))
  367.         FreeMem((char *)p, p->Size);
  368.     Allocp = NULLHDR;
  369.     Availmem = 0;
  370.     Heapsize = 0;
  371. }
  372.  
  373. static void
  374. freeblocks(void)
  375. {
  376.     struct MBH {    /* Layout of memory region */
  377.         struct MemBlock m;
  378.         HEADER        h;
  379.     } *m, *n;
  380.  
  381.     if (--Delayfree >= 0)
  382.         return;
  383.  
  384.     Delayfree = 128;
  385.  
  386.     for (m = (struct MBH *)SysBlocks.mlh_Head;
  387.          n = (struct MBH *)m->m.Node.mln_Succ; m = n) {
  388.         int size;
  389.  
  390.         if (m->h.s.ptr == &m->h)    /* Is he really free memory? */
  391.         continue;
  392.         size = m->h.s.size * ABLKSIZE;
  393.                         /* Does he go all the way? */
  394.         if (m->m.Size == size + sizeof(struct MemBlock)) {
  395.         void *v;
  396.  
  397.         v = malloc(size - ABLKSIZE);    /* unlink from freelist */
  398.         if (v != (m + 1)) {
  399.             free(v);
  400.             continue;
  401.         }
  402.         Remove((struct Node *)&m->m.Node);
  403.  
  404.         Heapsize -= size;
  405.         Allocs--;        /* nullify increment inside malloc() */
  406.         FreeMem((char *)m, m->m.Size);
  407.  
  408.         return;
  409.         }
  410.     }
  411. }
  412. #endif
  413.  
  414. #ifdef    AMIGA    /* Not presently used by pc */
  415. /* Move existing block to new area */
  416. void *
  417. realloc(area,size)
  418. void *area;
  419. unsigned size;
  420. {
  421.     unsigned osize;
  422.     HEADER HUGE *hp;
  423.     char HUGE *cp;
  424.  
  425.     hp = ((HEADER *)area) - 1;
  426.     osize = (hp->s.size -1) * ABLKSIZE;
  427.  
  428.     free(area);
  429.     if((cp = malloc(size)) != NULL && cp != area)
  430.         memcpy((char *)cp,(char *)area,size>osize? osize : size);
  431.     return cp;
  432. }
  433. #endif
  434. /* Allocate block of cleared memory */
  435. void *
  436. calloc(nelem,size)
  437. unsigned nelem; /* Number of elements */
  438. unsigned size;    /* Size of each element */
  439. {
  440.     register unsigned i;
  441.     register char *cp;
  442.  
  443.     i = nelem * size;
  444.     if((cp = malloc(i)) != NULL)
  445.         memset(cp,0,i);
  446.     return cp;
  447. }
  448. /* Version of malloc() that waits if necessary for memory to become available */
  449. void *
  450. mallocw(nb)
  451. unsigned nb;
  452. {
  453.     register void *p;
  454.  
  455.     while((p = malloc(nb)) == NULL){
  456.         Memwait++;
  457.         pwait(&Memwait);
  458.         Memwait--;
  459.     }
  460.     return p;
  461. }
  462. /* Version of calloc that waits if necessary for memory to become available */
  463. void *
  464. callocw(nelem,size)
  465. unsigned nelem; /* Number of elements */
  466. unsigned size;    /* Size of each element */
  467. {
  468.     register unsigned i;
  469.     register char *cp;
  470.  
  471.     i = nelem * size;
  472.     cp = mallocw(i);
  473.     memset(cp,0,i);
  474.     return cp;
  475. }
  476. /* Return 0 if at least Memthresh memory is available. Return 1 if
  477.  * less than Memthresh but more than Memthresh/2 is available; i.e.,
  478.  * if a yellow garbage collection should be performed. Return 2 if
  479.  * less than Memthresh/2 is available, i.e., a red collection should
  480.  * be performed.
  481.  */
  482. int
  483. availmem()
  484. {
  485.     void *p;
  486.  
  487.     if(Availmem*ABLKSIZE >= Memthresh)
  488.         return 0;    /* We're clearly OK */
  489.  
  490.     /* There's not enough on the heap; try calling malloc to see if
  491.      * it can get more from the system
  492.      */
  493.     if((p = malloc(Memthresh)) != NULL){
  494.         free(p);
  495.         return 0;    /* Okay */
  496.     }
  497.     if((p = malloc(Memthresh/2)) != NULL){
  498.         free(p);
  499.         return 1;    /* Yellow alert */
  500.     }
  501.     return 2;        /* Red alert */
  502. }
  503.  
  504. /* Print heap stats */
  505. static int
  506. dostat(argc,argv,envp)
  507. int argc;
  508. char *argv[];
  509. void *envp;
  510. {
  511.     struct sysblock *sp;
  512.     int i;
  513.  
  514.     printf("heap size %lu avail %lu (%lu%%) morecores %lu\n",
  515.      Heapsize,Availmem * ABLKSIZE,100L*Availmem*ABLKSIZE/Heapsize,
  516.      Morecores);
  517. #ifdef MSDOS
  518.     if(Sysblock[0].npar != 0){
  519.         printf("Extra blocks:");
  520.         for(i=0,sp=Sysblock;i< NSYSBLOCK;i++,sp++){
  521.             if(sp->npar == 0)
  522.                 break;
  523.             printf(" (%x0-%x0)",sp->seg,sp->seg+sp->npar);
  524.         }
  525.         printf("\n");
  526.     }
  527. #endif
  528. #ifdef AMIGA
  529.     {
  530.         struct MemBlock *m;
  531.  
  532.         printf("Extra blocks:");
  533.         m = (struct MemBlock *)&SysBlocks;
  534.         while (m = NextNode(m)) {
  535.             printf(" (%06x-%06x)", m, (char *)m + m->Size);
  536.         }
  537.         printf("\n");
  538.     }
  539. #endif
  540.     printf("allocs %lu frees %lu (diff %lu) alloc fails %lu invalid frees %lu\n",
  541.         Allocs,Frees,Allocs-Frees,Memfail,Invalid);
  542.     printf("pushdown calls %lu pushdown calls to malloc %lu\n",
  543.         Pushdowns,Pushalloc);
  544.     printf("interrupts-off calls to malloc %lu free %lu\n",Intalloc,Intfree);
  545.     printf("garbage collections yellow %lu red %lu\n",Yellows,Reds);
  546.     iqstat();
  547.     return 0;
  548. }
  549.  
  550. /* Print heap free list */
  551. static int
  552. dofreelist(argc,argv,envp)
  553. int argc;
  554. char *argv[];
  555. void *envp;
  556. {
  557.     HEADER HUGE *p;
  558.     int i = 0;
  559.  
  560.     for(p = Base.s.ptr;p != (HEADER HUGE *)&Base;p = p->s.ptr){
  561.         printf("%6lx %6lu",ptol((void *)p),p->s.size * ABLKSIZE);
  562.         if(++i == 4){
  563.             i = 0;
  564.             if(printf("\n") == EOF)
  565.                 return 0;
  566.         } else
  567.             printf(" | ");
  568.     }
  569.     if(i != 0)
  570.         printf("\n");
  571.     return 0;
  572. }
  573. static int
  574. dosizes(argc,argv,p)
  575. int argc;
  576. char *argv[];
  577. void *p;
  578. {
  579.     int i;
  580.  
  581.     for(i=0;i<16;i += 4){
  582.         printf("N>=%5u:%7ld| N>=%5u:%7ld| N>=%5u:%7ld| N>=%5u:%7ld\n",
  583.          1<<i,Sizes[i], 2<<i,Sizes[i+1],
  584.          4<<i,Sizes[i+2],8<<i,Sizes[i+3]);
  585.     }
  586.     return 0;
  587. }
  588. int
  589. domem(argc,argv,p)
  590. int argc;
  591. char *argv[];
  592. void *p;
  593. {
  594.     return subcmd(Memcmds,argc,argv,p);
  595. }
  596.  
  597. static int
  598. donibufs(argc,argv,p)
  599. int argc;
  600. char *argv[];
  601. void *p;
  602. {
  603.     return setint(&Nibufs,"Interrupt pool buffers",argc,argv);
  604. }
  605. static int
  606. doibufsize(argc,argv,p)
  607. int argc;
  608. char *argv[];
  609. void *p;
  610. {
  611.     return setuns(&Ibufsize,"Interrupt buffer size",argc,argv);
  612. }
  613.  
  614. static int
  615. dothresh(argc,argv,p)
  616. int argc;
  617. char *argv[];
  618. void *p;
  619. {
  620.     return setlong(&Memthresh,"Free memory threshold (bytes)",argc,argv);
  621. }
  622.  
  623. /* Background memory compactor, used when memory runs low */
  624. void
  625. gcollect(i,v1,v2)
  626. int i;    /* Args not used */
  627. void *v1;
  628. void *v2;
  629. {
  630.     void (**fp)__ARGS((int));
  631.     int red;
  632.  
  633.     for(;;){
  634.         pause(1000L);   /* Run every second */
  635.         /* If memory is low, collect some garbage. If memory is VERY
  636.          * low, invoke the garbage collection routines in "red" mode.
  637.          */
  638.         switch(availmem()){
  639.         case 0:
  640.             continue;    /* All is well */
  641.         case 1:
  642.             red = 0;
  643.             Yellows++;
  644.             break;
  645.         case 2:
  646.             red = 1;
  647.             Reds++;
  648.             break;
  649.         }
  650.         for(fp = Gcollect;*fp != NULL;fp++)
  651.             (**fp)(red);
  652.     }
  653. }
  654.